/**
//根据一棵树的中序遍历与后序遍历构造二叉树。 
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
// Related Topics 树 数组 哈希表 分治 二叉树 👍 625 👎 0

*/

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

public class ID00106ConstructBinaryTreeFromInorderAndPostorderTraversal {
public static void main(String[] args) {
Solution solution = new ID00106ConstructBinaryTreeFromInorderAndPostorderTraversal().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        return assembleTreeNode(inorder, 0, inorder.length -1, postorder, 0, postorder.length -1);

    }

    public TreeNode assembleTreeNode(int[] inorder, int iFrom, int iTo, int[] postorder, int pFrom, int pTo){
        if(iFrom == iTo && pFrom == pTo) return new TreeNode(postorder[pTo]);
        if(iFrom > iTo || pFrom > pTo) return null;

        //后序遍历的尾部找到根节点，
        int rootVal = postorder[pTo];
        TreeNode root = new TreeNode(rootVal); //后序最后一个为根节点

        //中序遍历分辨左右子树
        int rootIndex = 0;
        while(rootIndex <= iTo){
            if(inorder[iFrom + rootIndex] == rootVal){
                break;//找到root啦！
            }
            rootIndex++;
        }
        //左子树[iFrom : iFrom + rootIndex -1], [ pFrom，pFrom + rootIndex - 1]
        //中后序左子树长度一样，都是 rootIndex -1；
        root.left = assembleTreeNode(inorder, iFrom, iFrom + rootIndex -1, postorder, pFrom, pFrom + rootIndex -1 );

        //右子树 [ iFrom + rootIndex + 1 : iTo],  [ pFrom + rootIndex, pTo -1]
        root.right = assembleTreeNode(inorder, iFrom + rootIndex + 1, iTo, postorder, pFrom + rootIndex, pTo -1);

        return  root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)




}